{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Fertile Pyramids in a Land"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPyramids"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计农场中肥沃金字塔的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有一个 <strong>矩形网格</strong>&nbsp;状的农场，划分为&nbsp;<code>m</code>&nbsp;行&nbsp;<code>n</code>&nbsp;列的单元格。每个格子要么是 <strong>肥沃的</strong>&nbsp;（用 <code>1</code>&nbsp;表示），要么是 <strong>贫瘠</strong>&nbsp;的（用 <code>0</code>&nbsp;表示）。网格图以外的所有与格子都视为贫瘠的。</p>\n",
    "\n",
    "<p>农场中的&nbsp;<strong>金字塔</strong>&nbsp;区域定义如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>区域内格子数目 <strong>大于&nbsp;</strong><code>1</code>&nbsp;且所有格子都是 <strong>肥沃的</strong>&nbsp;。</li>\n",
    "\t<li>金字塔 <strong>顶端</strong>&nbsp;是这个金字塔 <strong>最上方</strong>&nbsp;的格子。金字塔的高度是它所覆盖的行数。令&nbsp;<code>(r, c)</code>&nbsp;为金字塔的顶端且高度为 <code>h</code>&nbsp;，那么金字塔区域内包含的任一格子&nbsp;<code>(i, j)</code>&nbsp;需满足&nbsp;<code>r &lt;= i &lt;= r + h - 1</code>&nbsp;<strong>且</strong>&nbsp;<code>c - (i - r) &lt;= j &lt;= c + (i - r)</code>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>一个 <strong>倒金字塔</strong>&nbsp;类似定义如下：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>区域内格子数目 <strong>大于</strong>&nbsp;<code>1</code>&nbsp;且所有格子都是 <b>肥沃的</b>&nbsp;。</li>\n",
    "\t<li>倒金字塔的 <strong>顶端</strong>&nbsp;是这个倒金字塔 <strong>最下方</strong>&nbsp;的格子。倒金字塔的高度是它所覆盖的行数。令&nbsp;<code>(r, c)</code>&nbsp;为金字塔的顶端且高度为 <code>h</code>&nbsp;，那么金字塔区域内包含的任一格子&nbsp;<code>(i, j)</code>&nbsp;需满足&nbsp;<code>r - h + 1 &lt;= i &lt;= r</code> <strong>且</strong> <code>c - (r - i) &lt;= j &lt;= c + (r - i)</code>&nbsp;。</li>\n",
    "</ol>\n",
    "\n",
    "<p>下图展示了部分符合定义和不符合定义的金字塔区域。黑色区域表示肥沃的格子。</p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/11/08/image.png\" style=\"width: 700px; height: 156px;\"></p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始且大小为 <code>m x n</code>&nbsp;的二进制矩阵&nbsp;<code>grid</code>&nbsp;，它表示农场，请你返回 <code>grid</code>&nbsp;中金字塔和倒金字塔的&nbsp;<strong>总数目</strong>&nbsp;。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg11.png\" style=\"width: 200px; height: 102px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/exa12.png\" style=\"width: 200px; height: 102px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/exa13.png\" style=\"width: 200px; height: 102px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[0,1,1,0],[1,1,1,1]]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "2 个可能的金字塔区域分别如上图蓝色和红色区域所示。\n",
    "这个网格图中没有倒金字塔区域。\n",
    "所以金字塔区域总数为 2 + 0 = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg21.png\" style=\"width: 180px; height: 122px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/exa22.png\" style=\"width: 180px; height: 122px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/exa23.png\" style=\"width: 180px; height: 122px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,1,1],[1,1,1]]\n",
    "<b>输出：</b>2\n",
    "<strong>解释：</strong>\n",
    "金字塔区域如上图蓝色区域所示，倒金字塔如上图红色区域所示。\n",
    "所以金字塔区域总数目为 1 + 1 = 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg3.png\" style=\"width: 149px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,0,1],[0,0,0],[1,0,1]]\n",
    "<b>输出：</b>0\n",
    "<strong>解释：</strong>\n",
    "网格图中没有任何金字塔或倒金字塔区域。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg41.png\" style=\"width: 180px; height: 144px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg42.png\" style=\"width: 180px; height: 144px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg43.png\" style=\"width: 180px; height: 144px;\">&nbsp;<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/10/23/eg44.png\" style=\"width: 180px; height: 144px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]\n",
    "<b>输出：</b>13\n",
    "<strong>解释：</strong>\n",
    "有 7 个金字塔区域。上图第二和第三张图中展示了它们中的 3 个。\n",
    "有 6 个倒金字塔区域。上图中最后一张图展示了它们中的 2 个。\n",
    "所以金字塔区域总数目为 7 + 6 = 13.\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>grid[i][j]</code>&nbsp;要么是&nbsp;<code>0</code>&nbsp;，要么是&nbsp;<code>1</code> 。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-fertile-pyramids-in-a-land](https://leetcode.cn/problems/count-fertile-pyramids-in-a-land/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-fertile-pyramids-in-a-land](https://leetcode.cn/problems/count-fertile-pyramids-in-a-land/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1,1,0],[1,1,1,1]]', '[[1,1,1],[1,1,1]]', '[[1,1,1,1,0],[1,1,1,1,1],[1,1,1,1,1],[0,1,0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = 0\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        # 正\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    f[i][j] = -1\n",
    "                else:\n",
    "                    if i == m-1 or j == 0 or j == n-1:\n",
    "                        f[i][j] = 0\n",
    "                    else:\n",
    "                        f[i][j] = min(f[i+1][j],f[i+1][j-1],f[i+1][j+1])+1\n",
    "                        ans += f[i][j]\n",
    "        \n",
    "        for i in range(0,m,1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    f[i][j] = -1\n",
    "                else:\n",
    "                    if i == 0 or j == 0 or j == n-1:\n",
    "                        f[i][j] = 0\n",
    "                    else:\n",
    "                        f[i][j] = min(f[i-1][j],f[i-1][j-1],f[i-1][j+1])+1\n",
    "                        ans += f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        a = grid[m-1]\n",
    "        for i in reversed(range(m-1)):\n",
    "            b = grid[i].copy()\n",
    "            for j in range(1, n - 1):\n",
    "                if b[j]:\n",
    "                    x = min(a[j-1], a[j], a[j+1])\n",
    "                    count += x\n",
    "                    b[j] += x\n",
    "            a = b\n",
    "        a = grid[0]\n",
    "        for i in range(1, m):\n",
    "            b = grid[i].copy()\n",
    "            for j in range(1, n - 1):\n",
    "                if b[j]:\n",
    "                    x = min(a[j-1], a[j], a[j+1])\n",
    "                    count += x\n",
    "                    b[j] += x\n",
    "            a = b\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [-1] * n \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            new = [-1] * n \n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    new[j] = min(dp[j - 1] if j > 0 else - 1, dp[j], dp[j + 1] if j < n - 1 else - 1) + 1\n",
    "                    res += new[j]\n",
    "            dp = new \n",
    "        \n",
    "        dp = [-1] * n \n",
    "        for i in range(m - 1, - 1, - 1):\n",
    "            new = [-1] * n \n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    new[j] = min(dp[j - 1] if j > 0 else - 1, dp[j], dp[j + 1] if j < n - 1 else - 1) + 1\n",
    "                    res += new[j]\n",
    "            dp = new \n",
    "        return res \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        # 金字塔\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    f[i][j] = -1\n",
    "                elif i == m - 1 or j == 0 or j == n - 1:\n",
    "                    f[i][j] = 0\n",
    "                else:\n",
    "                    f[i][j] = min(f[i + 1][j - 1], f[i + 1][j], f[i + 1][j + 1]) + 1\n",
    "                    ans += f[i][j]\n",
    "        \n",
    "        # 倒金字塔\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    f[i][j] = -1\n",
    "                elif i == 0 or j == 0 or j == n - 1:\n",
    "                    f[i][j] = 0\n",
    "                else:\n",
    "                    f[i][j] = min(f[i - 1][j - 1], f[i - 1][j], f[i - 1][j + 1]) + 1\n",
    "                    ans += f[i][j]\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        def f():\n",
    "            nonlocal ans\n",
    "            dp[-1] = grid[-1].copy()\n",
    "            for i in range(m-2,-1,-1):\n",
    "                dp[i][0] = grid[i][0]\n",
    "                dp[i][n-1] = grid[i][n-1]\n",
    "                for j in range(1,n-1):\n",
    "                    if grid[i][j] == 0:\n",
    "                        dp[i][j] = 0\n",
    "                    else:\n",
    "                        dp[i][j] = min(dp[i+1][j],dp[i+1][j-1],dp[i+1][j+1]) + 1\n",
    "                        ans += dp[i][j] - 1\n",
    "        f()\n",
    "        for i in range(m // 2):\n",
    "            grid[i],grid[m-1-i] = grid[m-1-i], grid[i]\n",
    "        f()\n",
    "        return ans\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0 for i in range(n)] for i in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == m-1 or j == 0 or j == n-1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min([dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]]) + 1\n",
    "                    ans += dp[i][j]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == 0 or j == 0 or j == n-1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min([dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]]) + 1\n",
    "                    ans += dp[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # dp[i][j] height of pyramid with top grid[i][j]\n",
    "        # height of pyramid is # of pyramids with top grid[i][j]\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        res = 0\n",
    "\n",
    "        # pyramid\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == m - 1 or j == 0 or j == n - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1\n",
    "                    res += dp[i][j]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == 0 or j == 0 or j == n - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + 1\n",
    "                    res += dp[i][j]\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        f=[[0]*n for _ in range(m)]\n",
    "        ans=0\n",
    "        #DP计算正金字塔的数目,考虑状态转移行数倒序枚举\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0: f[i][j]=-1\n",
    "                elif i==m-1 or j==0 or j==n-1: f[i][j]=0\n",
    "                else:\n",
    "                    f[i][j]=min(f[i+1][j-1],f[i+1][j],f[i+1][j+1])+1\n",
    "                    ans+=f[i][j]\n",
    "        #DP计算倒金字塔的数目,考虑状态转移行数正序枚举\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==0: f[i][j]=-1\n",
    "                elif i==0 or j==0 or j==n-1: f[i][j]=0\n",
    "                else:\n",
    "                    f[i][j]=min(f[i-1][j-1],f[i-1][j],f[i-1][j+1])+1\n",
    "                    ans+=f[i][j]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        def f(grid):\n",
    "            m,n = len(grid),len(grid[0])\n",
    "            F = [[-1] * n for i in range(m)]\n",
    "            for idx,i in enumerate(grid[-1]):\n",
    "                if i:F[-1][idx] = 0\n",
    "            for i in range(m-2,-1,-1):\n",
    "                F[i][0] = 0 if grid[i][0] else -1\n",
    "                F[i][-1] = 0 if grid[i][-1] else -1\n",
    "                for j in range(1,n-1):\n",
    "                    if not grid[i][j]:continue\n",
    "                    F[i][j] = min(F[i+1][j-1],F[i+1][j],F[i+1][j+1])+1\n",
    "            res = 0\n",
    "            \n",
    "            for l in F:\n",
    "                for i in l:\n",
    "                    if i>0:res += i\n",
    "            return res\n",
    "        return f(grid) + f(grid[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m,n = len(grid), len(grid[0])\n",
    "\n",
    "        dp = [[-1]*(n+1) for _ in range(m)]\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if i==m-1 and grid[i][j]==1:\n",
    "                    dp[i][j] = 0 \n",
    "                    continue \n",
    "                if grid[i][j]==1:\n",
    "                    dp[i][j] = min(dp[i+1][j-1], dp[i+1][j],dp[i+1][j+1])+1\n",
    "                    ans += dp[i][j]\n",
    "        \n",
    "        new_grid = []\n",
    "        dp = [[-1]*(n+1) for _ in range(m)]\n",
    "        for i in range(m-1,-1,-1):\n",
    "            new_grid.append(grid[i])\n",
    "        \n",
    "        for i in range(m-1,-1,-1):\n",
    "            for j in range(n-1,-1,-1):\n",
    "                if i==m-1 and new_grid[i][j]==1:\n",
    "                    dp[i][j] = 0 \n",
    "                    continue \n",
    "                if new_grid[i][j]==1:\n",
    "                    dp[i][j] = min(dp[i+1][j-1], dp[i+1][j],dp[i+1][j+1])+1\n",
    "                    ans += dp[i][j]\n",
    "        return ans \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        ans = 0\n",
    "\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == m-1 or j == 0 or j == n-1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1\n",
    "                    ans += dp[i][j]\n",
    "\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp[i][j] = -1\n",
    "                elif i == 0 or j == 0 or j == n-1:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i-1][j+1]) + 1\n",
    "                    ans += dp[i][j]\n",
    "\n",
    "        return ans\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp1 = [[0]*n for _ in range(m)]\n",
    "        dp2 = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            ri = m-1-i\n",
    "            for j in range(n):\n",
    "                if i==m-1:\n",
    "                    dp1[i][j] = 1 if grid[i][j]==1 else 0\n",
    "                else:\n",
    "                    if j==0 or j==n-1:\n",
    "                        dp1[i][j] = 1 if grid[i][j]==1 else 0\n",
    "                    else:\n",
    "                        if grid[i][j] == 1:\n",
    "                            dp1[i][j] = 1\n",
    "                            if grid[i+1][j]==1:\n",
    "                                dp1[i][j] += min(dp1[i+1][j-1], dp1[i+1][j+1])\n",
    "                \n",
    "                if ri==0:\n",
    "                    dp2[ri][j] = 1 if grid[ri][j]==1 else 0\n",
    "                else:\n",
    "                    if j==0 or j==n-1:\n",
    "                        dp2[ri][j] = 1 if grid[ri][j]==1 else 0\n",
    "                    else:\n",
    "                        if grid[ri][j] == 1:\n",
    "                            dp2[ri][j] = 1\n",
    "                            if grid[ri-1][j]==1:\n",
    "                                dp2[ri][j] += min(dp2[ri-1][j-1], dp2[ri-1][j+1])\n",
    "\n",
    "        total = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp1[i][j]>1:\n",
    "                    total += (dp1[i][j] - 1)\n",
    "                if dp2[i][j]>1:\n",
    "                    total += (dp2[i][j] - 1)\n",
    "                pass \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        ans = 0\n",
    "        dp = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    pre = []\n",
    "                    for x, y in [[i-1, j-1], [i-1, j], [i-1, j+1]]:\n",
    "                        if 0<=x<m and 0<=y<n:\n",
    "                            pre.append(dp[x][y])\n",
    "                        else:\n",
    "                            pre.append(0)\n",
    "                    dp[i][j] = min(pre) + 1\n",
    "                    ans += dp[i][j] - 1\n",
    "        \n",
    "        grid = grid[::-1]\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    pre = []\n",
    "                    for x, y in [[i - 1, j - 1], [i - 1, j], [i - 1, j + 1]]:\n",
    "                        if 0 <= x < m and 0 <= y < n:\n",
    "                            pre.append(dp[x][y])\n",
    "                        else:\n",
    "                            pre.append(0)\n",
    "                    dp[i][j] = min(pre) + 1\n",
    "                    ans += dp[i][j] - 1\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        # 大金字塔由小金字塔递推得来，以金字塔的顶端坐标以及金字塔的高度取描述金字塔\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp1 = [[0]*n for _ in range(m)]\n",
    "        dp2 = [[0]*n for _ in range(m)]\n",
    "\n",
    "        for i in range(m-1, -1, -1):\n",
    "            ri = m-1-i\n",
    "            for j in range(n):\n",
    "                if i==m-1:\n",
    "                    dp1[i][j] = 1 if grid[i][j]==1 else 0\n",
    "                else:\n",
    "                    if j==0 or j==n-1:\n",
    "                        dp1[i][j] = 1 if grid[i][j]==1 else 0\n",
    "                    else:\n",
    "                        if grid[i][j] == 1:\n",
    "                            dp1[i][j] = 1\n",
    "                            if grid[i+1][j]==1:\n",
    "                                dp1[i][j] += min(dp1[i+1][j-1], dp1[i+1][j+1])\n",
    "                \n",
    "                if ri==0:\n",
    "                    dp2[ri][j] = 1 if grid[ri][j]==1 else 0\n",
    "                else:\n",
    "                    if j==0 or j==n-1:\n",
    "                        dp2[ri][j] = 1 if grid[ri][j]==1 else 0\n",
    "                    else:\n",
    "                        if grid[ri][j] == 1:\n",
    "                            dp2[ri][j] = 1\n",
    "                            if grid[ri-1][j]==1:\n",
    "                                dp2[ri][j] += min(dp2[ri-1][j-1], dp2[ri-1][j+1])\n",
    "\n",
    "        total = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if dp1[i][j]>1:\n",
    "                    total += (dp1[i][j] - 1)\n",
    "                if dp2[i][j]>1:\n",
    "                    total += (dp2[i][j] - 1)\n",
    "                pass \n",
    "        return total"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        zheng, dao = [[0]*n for _ in range(m)], [[0]*n for _ in range(m)]\n",
    "        res = 0\n",
    "        for i in range(1, m):\n",
    "            for j in range(2, n):\n",
    "                if min(grid[i][j], grid[i-1][j-1], grid[i][j-1], grid[i][j-2]):\n",
    "                    zheng[i][j] = min(zheng[i-1][j-1], zheng[i][j-1], zheng[i][j-2]) + 1\n",
    "                    res += zheng[i][j]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for j in range(2, n):\n",
    "                if min(grid[i][j], grid[i][j-1], grid[i][j-2], grid[i+1][j-1]):\n",
    "                    dao[i][j] = min(dao[i][j-1], dao[i][j-2], dao[i+1][j-1]) + 1\n",
    "                    res += dao[i][j]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        # dp[i][j] height of pyramid, height is # of pyramids with top grid[i][j]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        res = 0\n",
    "        # pyramid\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n):\n",
    "                # initialized -1 for non fertile for easier transition\n",
    "                if grid[i][j] == 0: \n",
    "                    dp[i][j] = -1\n",
    "                # val 1 but at the boarder\n",
    "                elif i == m - 1 or j == 0 or j == n - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:   # val 1 not at boarder\n",
    "                    dp[i][j] = min(dp[i + 1][j - 1], dp[i + 1][j], dp[i + 1][j + 1]) + 1\n",
    "                    res += dp[i][j]\n",
    "\n",
    "        # reverse pyramid\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                # initialized -1 for non fertile for easier transition\n",
    "                if grid[i][j] == 0: \n",
    "                    dp[i][j] = -1\n",
    "                # val 1 but at the boarder\n",
    "                elif i == 0 or j == 0 or j == n - 1:\n",
    "                    dp[i][j] = 0\n",
    "                else:   # val 1 not at boarder\n",
    "                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]) + 1\n",
    "                    res += dp[i][j]\n",
    "        return res\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        dirs = [[1,1],[1,0],[1,-1]]\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        res = 0\n",
    "        for i in range(n - 1,-1,-1) :\n",
    "            for j in range(m - 1,-1,-1) :\n",
    "                if grid[i][j] == 1 :\n",
    "                    f[i][j] = 1\n",
    "                    if i == n - 1 or j - 1 < 0 or j + 1 >= m :\n",
    "                        continue\n",
    "                    mi = inf\n",
    "                    for t in range(j-1,j+2) :\n",
    "                        mi = min(f[i + 1][t],mi)\n",
    "                    f[i][j] += mi\n",
    "                    res += f[i][j] - 1\n",
    "        print(res,f)\n",
    "        f = [[0] * m for _ in range(n)]\n",
    "        for i in range(0,n) :\n",
    "            for j in range(0,m) :\n",
    "                if grid[i][j] == 1 :\n",
    "                    f[i][j] = 1\n",
    "                    if i == 0 or j - 1 < 0 or j + 1 >= m :\n",
    "                        continue\n",
    "                    mi = inf\n",
    "                    for t in range(j-1,j+2) :\n",
    "                        mi = min(f[i - 1][t],mi)\n",
    "                    f[i][j] += mi\n",
    "                    res += f[i][j] - 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        # dp_u[i][j] 表示以grid[i][j]为顶的金字塔的高度 dp_dp[i][j] 反之\n",
    "        dp_u = [[grid[i][j] for j in range(n)] for i in range(m)]\n",
    "        dp_d = [[grid[i][j] for j in range(n)] for i in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(1, n - 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp_u[i][j] = 0\n",
    "                else:\n",
    "                    dp_u[i][j] = min(dp_u[i + 1][j - 1], dp_u[i + 1][j], dp_u[i + 1][j + 1]) + 1\n",
    "                    ans += dp_u[i][j] - 1\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n - 1):\n",
    "                if grid[i][j] == 0:\n",
    "                    dp_d[i][j] = 0\n",
    "                else:\n",
    "                    dp_d[i][j] = min(dp_d[i - 1][j - 1], dp_d[i - 1][j], dp_d[i - 1][j + 1]) + 1\n",
    "                    ans += dp_d[i][j] - 1\n",
    "        return ans\n",
    "\n",
    "    def countPyramids1(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        p_sum = [[0] + list(accumulate(grid[i])) for i in range(m)]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0: continue\n",
    "                for d in range(1, m - i):\n",
    "                    l, r = j - d, j + d\n",
    "                    if l < 0 or r > n - 1: break\n",
    "                    ss = p_sum[i + d][r + 1] - p_sum[i + d][l]\n",
    "                    if ss != d * 2 + 1: break\n",
    "                    ans += 1\n",
    "                for d in range(1, i + 1):\n",
    "                    l, r = j - d, j + d\n",
    "                    if l < 0 or r > n - 1: break\n",
    "                    ss = p_sum[i - d][r + 1] - p_sum[i - d][l]\n",
    "                    if ss != d * 2 + 1: break\n",
    "                    ans += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        # dp[i][j]表示(i, j)形成金字塔的层数\n",
    "        # g[i][j] = min(g[i-1][j], g[i-1][j-1], g[i-1][j+1]) + 1\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def dfs(g):\n",
    "            res = 0\n",
    "            for i in range(m - 2, -1, -1):\n",
    "                for j in range(1, n - 1):\n",
    "                    if grid[i][j] == 0: continue\n",
    "                    g[i][j] = min(g[i + 1][j], g[i + 1][j-1], g[i + 1][j+1]) + 1\n",
    "                    res += g[i][j] - 1\n",
    "            print(g)\n",
    "            return res\n",
    "        ans = 0\n",
    "        ans += dfs(deepcopy(grid))\n",
    "        # # 将矩阵反转\n",
    "        print(\"ok\", grid)\n",
    "        for i in range(m // 2):\n",
    "            grid[i], grid[m - 1 - i] = grid[m - 1 - i], grid[i]\n",
    "        print(grid)\n",
    "        ans += dfs(deepcopy(grid))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        # dp, dp[inverse]\n",
    "        # dp[r][c]: max height with grid[r][c] as apex\n",
    "        dp = [[1] * m for _ in range(n)]\n",
    "        dp_inv = [[1] * m for _ in range(n)]\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                dp[row][col] = 1 if grid[row][col] == 1 else 0\n",
    "                dp_inv[row][col] = 1 if grid[row][col] == 1 else 0\n",
    "        # for dp, count height bottom up\n",
    "        for row in range(n - 2, -1, -1):\n",
    "            for col in range(1, m - 1):\n",
    "                if grid[row][col] == 1 and grid[row + 1][col] == 1:\n",
    "                    dp[row][col] = min(dp[row + 1][col - 1], dp[row + 1][col + 1]) + 1\n",
    "        \n",
    "        # for reverse dp, count height top down\n",
    "        for row in range(1, n):\n",
    "            for col in range(1, m - 1):\n",
    "                if grid[row][col] == 1 and grid[row - 1][col] == 1:\n",
    "                    dp_inv[row][col] = min(dp_inv[row - 1][col - 1], dp_inv[row - 1][col + 1]) + 1\n",
    "        \n",
    "        res = 0\n",
    "        print(dp)\n",
    "        print(dp_inv)\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                if dp[row][col] > 0:\n",
    "                    res += (dp[row][col] - 1)\n",
    "                if dp_inv[row][col] > 0:\n",
    "                    res += (dp_inv[row][col] - 1)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        presum = [[0] * (m+1) for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(1,m+1):\n",
    "                presum[i][j] = presum[i][j-1] + grid[i][j-1]\n",
    "        \n",
    "        def check(r, c):\n",
    "            #print(\"check: \", r, c)\n",
    "            ans = 0\n",
    "            for i in range(r+1, n):\n",
    "                # c - (i - r) <= j <= c + (i - r)\n",
    "                s, e = c - (i - r), c + (i - r)\n",
    "                if s < 0 or e >= m:\n",
    "                    break\n",
    "                #print(presum[i][e+1]-presum[i][s], e - s + 1)\n",
    "                if presum[i][e+1]-presum[i][s] == e - s + 1:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    break\n",
    "            for i in range(r-1, -1, -1):\n",
    "                # c - (r - i) <= j <= c + (r - i)\n",
    "                s, e = c - (r - i), c + (r - i)\n",
    "                if s < 0 or e >= m:\n",
    "                    break\n",
    "                #print(presum[i][e+1]-presum[i][s], e - s + 1)\n",
    "                if presum[i][e+1]-presum[i][s] == e - s + 1:\n",
    "                    ans += 1\n",
    "                else:\n",
    "                    break\n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += check(i, j)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        res = 0\n",
    "        t1 = [[grid[i][j] for j in range(m)] for i in range(n) ]\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(m - 2, 0, -1):\n",
    "                if t1[i][j] != 1:\n",
    "                    continue\n",
    "                a = min(t1[i + 1][j - 1], t1[i + 1][j], t1[i + 1][j + 1])\n",
    "                if a > 0:\n",
    "                    res += a\n",
    "                    t1[i][j] += a\n",
    "        print(t1)\n",
    "        t2 = [[grid[i][j] for j in range(m)] for i in range(n) ]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m - 1):\n",
    "                if t2[i][j] != 1:\n",
    "                    continue\n",
    "                a = min(t2[i - 1][j + 1], t2[i - 1][j], t2[i - 1][j - 1])\n",
    "                if a > 0:\n",
    "                    res += a\n",
    "                    t2[i][j] += a\n",
    "        print(t2)\n",
    "        return res\n",
    "# 0,1,1,1,0\n",
    "# 1,1,1,1,1\n",
    "# 1,1,1,1,1\n",
    "# 1,0,1,0,1\n",
    "\n",
    "# 0,0,0,0,1,0,1,0,0,0\n",
    "# 0,0,0,1,1,1,1,1,0,0\n",
    "# 0,0,1,1,1,1,1,1,1,0\n",
    "# 0,1,1,1,1,1,1,1,1,0\n",
    "# 1,1,1,1,1,1,1,1,0,1\n",
    "# 1,1,1,1,1,1,1,1,1,1\n",
    "\n",
    "# [0, 0, 0, 0, 2, 0, 2, 0, 0, 0], \n",
    "# [0, 0, 0, 2, 2, 2, 2, 2, 0, 0],\n",
    "# [0, 0, 2, 2, 2, 2, 2, 2, 1, 0], \n",
    "# [0, 2, 2, 2, 2, 2, 2, 1, 1, 0], \n",
    "# [1, 2, 2, 2, 2, 2, 2, 2, 0, 1], \n",
    "# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        def f(grid):\n",
    "            m,n = len(grid),len(grid[0])\n",
    "            F = [[0] * (n+1) for i in range(m)]\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    F[i][j] = F[i][j-1]+grid[i][j]\n",
    "            res = 0\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if not grid[i][j]:continue\n",
    "                    cnt = 0\n",
    "                    l,r,d = j-1,j+1,1\n",
    "                    while l >= 0 and r < n and i+d < m and F[i+d][r]-F[i+d][l-1] == 2*d+1:\n",
    "                        d += 1;r += 1;l -= 1;cnt += 1\n",
    "                    res += cnt\n",
    "            # print(res)\n",
    "            return res\n",
    "        return f(grid) + f(grid[::-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        # 1 <= m, n <= 1000 ;; 前缀和\n",
    "        pre = [list(accumulate(row, initial=0)) for row in grid]\n",
    "        \n",
    "        ans = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    for k in range(1, n+1):\n",
    "                        left, right = j - k, j+k\n",
    "                        if left < 0 or right >= n or i-k < 0:\n",
    "                            break\n",
    "                        v = pre[i-k][right+1] - pre[i-k][left]\n",
    "                        if v != right - left + 1:\n",
    "                            break\n",
    "                    ans += k-1\n",
    "                if grid[i][j]:\n",
    "                    for k in range(1, n+1):\n",
    "                        left, right = j - k, j+k\n",
    "                        if left < 0 or right >= n or i+k >=m:\n",
    "                            break\n",
    "                        v = pre[i+k][right+1] - pre[i+k][left]\n",
    "                        if v != right - left + 1:\n",
    "                            break\n",
    "                    ans += k-1\n",
    "        \n",
    "        return ans\n",
    "                        \n",
    "                        \n",
    "                        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i][j + 1] = pre_sum[i][j] + grid[i][j]\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                x, y_left, y_right = i + 1, j - 1, j + 1\n",
    "                while x < m and y_left >= 0 and y_right < n:\n",
    "                    if pre_sum[x][y_right + 1] - pre_sum[x][y_left] == y_right - y_left + 1:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "                    x += 1\n",
    "                    y_left -= 1\n",
    "                    y_right += 1\n",
    "                x, y_left, y_right = i - 1, j - 1, j + 1\n",
    "                while x >= 0 and y_left >= 0 and y_right < n:\n",
    "                    if pre_sum[x][y_right + 1] - pre_sum[x][y_left] == y_right - y_left + 1:\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        break\n",
    "                    x -= 1\n",
    "                    y_left -= 1\n",
    "                    y_right += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        pres = []\n",
    "        m , n = len(grid) , len(grid[0])\n",
    "        for i in range(m):\n",
    "            pres.append(list(accumulate(grid[i],initial=0)))\n",
    "\n",
    "        def dfs(i,j,label,deep):\n",
    "            ni = i + label * deep\n",
    "            l , r = j - deep , j + deep + 1\n",
    "            if 0 <= ni < m and l >= 0 and r <= n and pres[ni][r] - pres[ni][l] == r - l:\n",
    "                return dfs(i,j,label,deep+1) + 1\n",
    "            return 0\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(1,n-1):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans += dfs(i,j,1,1) + dfs(i,j,-1,1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        def f(grid):\n",
    "            m,n = len(grid),len(grid[0])\n",
    "            dic = {}\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if (i==0) or (j==0) or (j==(n-1)):\n",
    "                        if grid[i][j]==1:\n",
    "                            dic[(i, j)] = 1\n",
    "                        else:\n",
    "                            dic[(i, j)] = 0     \n",
    "                    elif grid[i][j]==1:\n",
    "                        dic[(i, j)] = 1+min(dic[(i-1, j-1)], dic[(i-1, j)], dic[(i-1, j+1)]) \n",
    "                    else:\n",
    "                        dic[(i, j)] = 0 \n",
    "            tmp = [j-1 for j in dic.values() if j>1] + [0]\n",
    "            return sum(tmp)\n",
    "        return f(grid) + f(grid[::-1])\n",
    "\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPyramids(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        def cal(graph):\n",
    "            @cache\n",
    "            def dfs(i, j):\n",
    "                res = inf\n",
    "                if graph[i][j] == 1:\n",
    "                    for x, y in (i + 1, j - 1), (i + 1, j), (i + 1, j + 1):\n",
    "                        if 0 <= x < n and 0 <= y < m:\n",
    "                            if graph[x][y] == 1:\n",
    "                                res = min(res, dfs(x, y) + 1)\n",
    "                            else:\n",
    "                                return 1\n",
    "                        else:\n",
    "                            return 1\n",
    "                return res\n",
    "\n",
    "            ans = 0\n",
    "            for i in range(n - 1):\n",
    "                for j in range(1, m - 1):\n",
    "                    if graph[i][j] == 1:\n",
    "                        ans += dfs(i, j) - 1\n",
    "                        #print(i, j, dfs(i, j) - 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = cal(grid) \n",
    "        i, j = 0, n - 1\n",
    "        while i < j:\n",
    "            grid[i], grid[j] = grid[j], grid[i]\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        ans += cal(grid)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
